def sift(li,low,high):
    """

    :param li: 列表
    :param low: 堆根节点的位置
    :param high: 堆的最后一个元素位置
    :return:
    """
    i=low #i最开始指向根节点
    j=2*i+1 #左孩子
    tmp=li[low] #把堆顶存起来

    while j<=high: #只要j位置有数
        if j+1<=high and li[j+1]<li[j]: #如果右孩子存在并且比左孩子大
            j=j+1 #j指向右孩子
        if li[j]<tmp:
            li[i]=li[j]
            i=j #往下看一层
            j=2*i+1
        else: #tmp更大,把tmp放在i的位置上
            #li[i]=tmp #把tmp放在某一级领导的位置上
            break
    li[i]=tmp #把tmp放在叶子结点上

def topk(li,k):
    n=len(li)
    heap=li[0:k]
    #1:建堆
    for i in range((k-2)//2,-1,-1):
        sift(heap,i,k-1)
    #2:遍历
    for i in range(k,n-1):
        if li[i]>heap[0]:
            heap[0]=li[i]
            sift(heap,0,k-1)
    #3:输出
    for i in range(k-1,-1,-1):
        heap[i],heap[0]=heap[0],heap[i]
        sift(heap,0,i-1)
    return heap

def heap_sort(li):
    n=len(li)
    for i in range((n-2)//2,-1,-1):
        #i表示建堆的时候调整的部分的根的下标
        sift(li,i,n-1)
    for i in range(n-1,-1,-1):
        #i指向当前堆的最后一个元素
        li[0],li[i]=li[i],li[0]
        sift(li,0,i-1)
    return li
import random
li=[i for i in range(100)]
random.shuffle(li)
print(topk(li,10))